﻿using System;
using System.Collections.Generic;

namespace RoomyDungeonGenerator
{
	/// <summary>Static class for room based map generation.</summary>
	public static class MapGenerator
	{
		/// <summary>Rate at which the probability of connecting two rooms decreases by the number of entrances that the rooms already have.</summary>
		private const float _roomConnectionRegressionRate = 15.0f;

		/// <summary>
		/// Generates a new room-based dungeon.
		/// <para>
		/// The resulting map consists of rooms and corridors connecting the rooms. Each tile has a reference to its own coordinates, and the room it belongs to (if any).
		/// Each room has a list of entrances, and a list of rooms it is directly connected to.
		/// </para>
		/// </summary>
		/// <param name="seed">An integer used to seed the pseudorandom generator.</param>
		/// <param name="minRows">Minimum number of rows in the grid</param>
		/// <param name="maxRows">Maximum number of rows in the grid</param>
		/// <param name="minCols">Minimum number of columns in the grid</param>
		/// <param name="maxCols">Maximum number of columns in the grid</param>
		/// <param name="minRoomCount">Minimum number of rooms to attempt to generate.
		/// <para>The actual number of rooms generated may be lower than this if the map size is too small to fit the requested number of rooms.</para></param>
		/// <param name="maxRoomCount">The maximum number of rooms to generate.</param>
		/// <param name="minRoomSize">The lower bound to the width or height of a room</param>
		/// <param name="maxRoomSize">The upper bound to the width or height of a room</param>
		/// <param name="roomConnectionDistance">The maximum distance for two rooms to have a direct corridor between them</param>
		/// <param name="extraConnectionProbability">Percentage (0-100) probability of two nearby rooms to be connected with a direct corridor if they have no direct connections yet.
		/// <para>Decrease for more dead-ends, increase for more interconnected rooms.</para></param>
		public static Map Generate(int seed, int minRows = 25, int maxRows = 35, int minCols = 25, int maxCols = 35, int minRoomCount = 6, int maxRoomCount = 10, int minRoomSize = 3, int maxRoomSize = 6,
			int roomConnectionDistance = 3, int extraConnectionProbability = 60)
		{
			if (maxRows < minRows)
				maxRows = minRows;
			if (maxCols < minCols)
				maxCols = minCols;
			if (minRoomCount < 0)
				minRoomCount = 0;
			if (maxRoomCount < minRoomCount)
				maxRoomCount = minRoomCount;
			if (minRoomSize < 1 || maxRoomSize < 1)
				throw new ArgumentException("Room sizes have to be at least 1!");
			if (maxRoomSize < minRoomSize)
				maxRoomSize = minRoomSize;
			if (minRows <= 0 || maxRows <= 0 || minCols <= 0 || maxCols <= 0)
				throw new ArgumentException("Map row and column counts have to be at least 1 in both dimensions!");
			if (roomConnectionDistance < 0)
				roomConnectionDistance = 0;
			if (extraConnectionProbability < 0 || extraConnectionProbability > 100)
				throw new ArgumentException("The parameter extraConnectionProbability has to be between 0 and 100 (inclusive).");
			Random r = new Random(seed);
			List<Room> rooms = new List<Room>();
			int rows = r.Next(minRows, maxRows + 1);
			int cols = r.Next(minCols, maxCols + 1);
			Tile[,] tiles = new Tile[cols, rows];
			for (int j = 0; j < rows; j++)
			{
				for (int i = 0; i < cols; i++)
				{
					tiles[i, j] = new Tile()
					{
						Type = TileTypes.Void,
						X = i,
						Y = j
					};
				}
			}
			int[] checkedWallCellIndices = new int[rows * cols];
			int checkedWallCellsCount = 0;
			int targetRoomCount = r.Next(minRoomCount, maxRoomCount + 1);
			int w = minRoomSize + r.Next(maxRoomSize - minRoomSize + 1);
			int h = minRoomSize + r.Next(maxRoomSize - minRoomSize + 1);
			int wallCellCount = 0;
			if (targetRoomCount > 0)
				rooms.Add(PlaceRoom(tiles, cols, rows, (cols / 2) - (w / 2), (rows / 2) - (h / 2), w, h, -1, -1, ref wallCellCount, firstRoom: true));
			int placedRoomCount = rooms.Count;
			bool trySmallerWidth = false, trySmallerHeight = false, trySmallest = false, foundCandidate = false, roomPlaced = false, wallCellAlreadyChecked = false;
			int wallCellIndex = 0, candidateWallCellIndex = 0, candidateX = 0, candidateY = 0, roomX, roomY;
			while (placedRoomCount < targetRoomCount)
			{
				if (trySmallest)
					w = h = minRoomSize;
				else
				{
					w = trySmallerWidth ? minRoomSize : (minRoomSize + r.Next(maxRoomSize - minRoomSize + 1));
					h = trySmallerHeight ? minRoomSize : (minRoomSize + r.Next(maxRoomSize - minRoomSize + 1));
				}

				roomPlaced = false;
				checkedWallCellsCount = 0;
				do
				{
					do
					{
						wallCellAlreadyChecked = false;
						candidateWallCellIndex = r.Next(wallCellCount);
						for (int i = 0; i < checkedWallCellsCount; i++)
						{
							if (checkedWallCellIndices[i] == candidateWallCellIndex)
							{
								wallCellAlreadyChecked = true;
								break;
							}
						}
					} while (wallCellAlreadyChecked);
					checkedWallCellIndices[checkedWallCellsCount] = candidateWallCellIndex;
					checkedWallCellsCount++;
					foundCandidate = false;
					wallCellIndex = 0;
					for (int j = 0; j < rows; j++)
					{
						for (int i = 0; i < cols; i++)
						{
							if (tiles[i, j].Type == TileTypes.Wall && wallCellIndex++ == candidateWallCellIndex)
							{
								foundCandidate = true;
								candidateX = i;
								candidateY = j;
								break;
							}
						}
						if (foundCandidate)
							break;
					}
					if (foundCandidate && FindValidRoomLocation(tiles, cols, rows, candidateX, candidateY, w, h, r, out roomX, out roomY))
					{
						rooms.Add(PlaceRoom(tiles, cols, rows, roomX, roomY, w, h, candidateX, candidateY, ref wallCellCount));
						placedRoomCount++;
						roomPlaced = true;
					}
				} while (!roomPlaced && checkedWallCellsCount < wallCellCount);
				if (!roomPlaced)
				{
					if (!trySmallerHeight && !trySmallerWidth && !trySmallest)
					{
						trySmallerHeight = true;
						continue;
					}
					else if (!trySmallerWidth)
					{
						trySmallerWidth = true;
						continue;
					}
					else if (!trySmallest)
					{
						trySmallest = true;
						continue;
					}
					else
						break;
				}
			}
			Map result = new Map(tiles, rooms);
			if (roomConnectionDistance > 0 && extraConnectionProbability > 0)
				AddExtraCorridors(ref result, roomConnectionDistance, extraConnectionProbability, r);
			AddWallsToCorridorsAndCorners(ref result, rows, cols);
			return result;
		}

		/// <summary>Used by the FindValidRoomLocation method, sets the range of valid positions for a room location.</summary>
		private static void SetKValues(bool kValid, int k, ref int kmin, ref int kmax, ref bool prevKValid)
		{
			if (kValid)
			{
				if (!prevKValid)
					kmin = kmax = k;
				else
					kmax = k;
			}
			prevKValid = kValid;
		}

		/// <summary>
		/// Attempts to find a random valid room location with the given entrance and room size. (Does not place the room itself.)
		/// <para>If successful, returns true, and the selectedX, selectedY out parameters will contain the coordinates for the upper left corner of the valid room location.</para>
		/// </summary>
		/// <param name="tiles">The map grid</param>
		/// <param name="cols">The number of columns of the map grid</param>
		/// <param name="rows">The number of rows of the map grid</param>
		/// <param name="entranceX">The x-coordinate of the entrance</param>
		/// <param name="entranceY">The y-coordinate of the entrance</param>
		/// <param name="w">The width of the desired new room</param>
		/// <param name="h">The height of the desired new room</param>
		/// <param name="r">The pseudorandom generator to be used with the random selection from the possible locations</param>
		/// <param name="selectedX">The x-coordinate of the resulting position (upper left corner of the possible room location), if the operation was successful</param>
		/// <param name="selectedY">The y-coordinate of the resulting position (upper left corner of the possible room location), if the operation was successful</param>
		private static bool FindValidRoomLocation(Tile[,] tiles, int cols, int rows, int entranceX, int entranceY, int w, int h, System.Random r, out int selectedX, out int selectedY)
		{
			int k = 0;
			int kminA = 0, kminB = 0, kminC = 0, kminD = 0, kmaxA = 0, kmaxB = 0, kmaxC = 0, kmaxD = 0;
			bool kValidA = false, kValidB = false, kValidC = false, kValidD = false, prevKValidA = false, prevKValidB = false, prevKValidC = false, prevKValidD = false;
			while (k < h)
			{
				kValidA = CanPlaceRoom(tiles, cols, rows, entranceX - w, entranceY - k, w, h);
				SetKValues(kValidA, k, ref kminA, ref kmaxA, ref prevKValidA);
				kValidB = CanPlaceRoom(tiles, cols, rows, entranceX + 1, entranceY - k, w, h);
				SetKValues(kValidB, k, ref kminB, ref kmaxB, ref prevKValidB);
				k++;
			}

			k = 0;
			while (k < w)
			{
				kValidC = CanPlaceRoom(tiles, cols, rows, entranceX - k, entranceY - h, w, h);
				SetKValues(kValidC, k, ref kminC, ref kmaxC, ref prevKValidC);
				kValidD = CanPlaceRoom(tiles, cols, rows, entranceX - k, entranceY + 1, w, h);
				SetKValues(kValidD, k, ref kminD, ref kmaxD, ref prevKValidD);
				k++;
			}
			int rangeA = kmaxA - kminA;
			int rangeB = kmaxB - kminB;
			int rangeC = kmaxC - kminC;
			int rangeD = kmaxD - kminD;
			int rangeCount = 0;
			if (rangeA > 0)
				rangeCount++;
			if (rangeB > 0)
				rangeCount++;
			if (rangeC > 0)
				rangeCount++;
			if (rangeD > 0)
				rangeCount++;
			if (rangeCount > 0)
			{
				int selectedRange = rangeCount == 1 ? 0 : r.Next(rangeCount);
				int q = 0;
				if (rangeA > 0)
				{
					if (selectedRange == q)
					{
						selectedX = entranceX - w;
						selectedY = entranceY - r.Next(kminA, kmaxA + 1);
						return true;
					}
					else
						q++;
				}
				if (rangeB > 0)
				{
					if (selectedRange == q)
					{
						selectedX = entranceX + 1;
						selectedY = entranceY - r.Next(kminB, kmaxB + 1);
						return true;
					}
					else
						q++;
				}
				if (rangeC > 0)
				{
					if (selectedRange == q)
					{
						selectedX = entranceX - r.Next(kminC, kmaxC + 1);
						selectedY = entranceY - h;
						return true;
					}
					else
						q++;
				}
				if (rangeD > 0)
				{
					if (selectedRange == q)
					{
						selectedX = entranceX - r.Next(kminD, kmaxD + 1);
						selectedY = entranceY + 1;
						return true;
					}
					else
						q++;
				}
			}
			selectedX = selectedY = 0;
			return false;
		}

		/// <summary>
		/// Determines whether a room with the provided size (w, h) can be placed at the provided location (posX, posY).
		/// </summary>
		/// <param name="tiles">The map grid</param>
		/// <param name="cols">The number of columns of the map grid</param>
		/// <param name="rows">The number of rows of the map grid</param>
		/// <param name="posX">The x-coordinate of the upper left corner of the room position to test</param>
		/// <param name="posY">The y-coordinate of the upper left corner of the room position to test</param>
		/// <param name="w">The width of the desired room</param>
		/// <param name="h">The height of the desired room</param>
		private static bool CanPlaceRoom(Tile[,] tiles, int cols, int rows, int posX, int posY, int w, int h)
		{
			if (posX <= 0 || posY <= 0 || posX + w >= cols || posY + h >= rows)
				return false;
			for (int j = posY; j < posY + h; j++)
			{
				for (int i = posX; i < posX + w; i++)
				{
					if (tiles[i, j].Type != TileTypes.Void)
						return false;
				}
			}
			return true;
		}

		/// <summary>
		/// Converts the tiles of the given area to Floor tiles, and the surrounding tiles to Wall tiles. Also converts the entrance tile to Floor, and connects the newly created room to the room
		/// where the given entrance leads. Returns the created room.
		/// <para>It is recommended to check the area first, with the CanPlaceRoom method.</para>
		/// </summary>
		/// <param name="tiles">The map grid</param>
		/// <param name="cols">The number of columns of the map grid</param>
		/// <param name="rows">The number of rows of the map grid</param>
		/// <param name="x">The x-coordinate of the upper left corner of the room</param>
		/// <param name="y">The y-coordinate of the upper left corner of the room</param>
		/// <param name="w">The width of the room</param>
		/// <param name="h">The height of the room</param>
		/// <param name="entranceX">The x-coordinate of the entrance</param>
		/// <param name="entranceY">The y-coordinate of the entrance</param>
		/// <param name="wallCellCount">The number of wall cells to modify</param>
		/// <param name="firstRoom">True if this is the first room on the map (therefore no connection to other rooms is required, and there is no entrance)</param>
		private static Room PlaceRoom(Tile[,] tiles, int cols, int rows, int x, int y, int w, int h, int entranceX, int entranceY, ref int wallCellCount, bool firstRoom = false)
		{
			Room connectedRoom = null;
			if (!firstRoom)
			{
				for (int j = ((entranceY == 0) ? 0 : (entranceY - 1)); j < (entranceY >= rows ? (rows - 1) : (entranceY + 1)); j++)
				{
					for (int i = (entranceX == 0 ? 0 : (entranceX - 1)); i < (entranceX >= cols ? (cols - 1) : (entranceX + 1)); i++)
					{
						if (!(j == entranceY && i == entranceX) && tiles[i, j].Type == TileTypes.Floor)
						{
							connectedRoom = tiles[i, j].ContainingRoom;
							break;
						}
					}
					if (connectedRoom != null)
						break;
				}
			}
			Room room = new Room(x, y, w, h);
			room.ConnectedRooms.Add(connectedRoom);
			for (int j = y - 1; j <= y + h; j++)
			{
				for (int i = x - 1; i <= x + w; i++)
				{
					if (i < 0 || j < 0 || i > cols - 1 || j > rows - 1)
						continue;
					if (j == y - 1 || j == y + h
							|| i == x - 1 || i == x + w)
					{
						if (tiles[i, j].Type != TileTypes.Wall
								&& !((j == y - 1 && i == x - 1) //here corners are not converted into Wall tiles yet, because we still need to use Wall tiles to determine suitable positions for new room entrances,
								|| (j == y - 1 && i == x + w)	//and corners are not suitable for that.
								|| (j == y + h && i == x - 1)
								|| (j == y + h && i == x + w))
								&& !(i == entranceX && j == entranceY))
						{
							tiles[i, j].Type = TileTypes.Wall;
							wallCellCount++;
						}
					}
					else
					{
						tiles[i, j].Type = TileTypes.Floor;
						tiles[i, j].ContainingRoom = room;
					}
				}
			}
			if (!firstRoom)
			{
				tiles[entranceX, entranceY].Type = TileTypes.Floor;
				wallCellCount--;
			}
			return room;
		}

		/// <summary>
		/// Connects nearby rooms that have not been previously directly connected.
		/// </summary>
		/// <param name="map">The generated map</param>
		/// <param name="roomConnectionDistance">The maximum distance for two rooms to have a direct corridor between them</param>
		/// <param name="extraConnectionProbability">Percentage (0-100) probability of two nearby rooms to be connected with a direct corridor if they have no direct connections yet.
		/// <para>Decrease for more dead-ends, increase for more interconnected rooms.</para></param>
		/// <param name="r">The pseudorandom generator used to determine positions and chances of extra connections</param>
		private static void AddExtraCorridors(ref Map map, int roomConnectionDistance, int extraConnectionProbability, System.Random r)
		{
			int prob = extraConnectionProbability;
			foreach (Room room in map.Rooms)
			{
				prob = extraConnectionProbability;
				if (room.Entrances.Count > 1)
				{
					prob -= (int)((room.Entrances.Count - 1) * _roomConnectionRegressionRate);
					if (prob < 0)
						prob = 0;
				}
				foreach (Room room2 in map.Rooms)
				{
					if (!room2.Equals(room) && !room.ConnectedRooms.Contains(room2))
					{
						bool connected = false;
						for (int i = room2.X; i < room2.X + room2.W; i++)
						{
							for (int j = room2.Y; j < room2.Y + room2.H; j++)
							{
								if (i >= room.X && i < room.X + room.W)
								{
									if (room.Y > j && room.Y - j <= roomConnectionDistance
											&& map.Tiles[i, j + 1].Type != TileTypes.Floor)
									{
										if (r.Next(101) <= prob)
										{
											for (int k = j + 1; k < room.Y; k++)
											{     //top
												map.Tiles[i, k].Type = TileTypes.Floor;
												room.Entrances.Add(map.Tiles[i, k]);
												room2.Entrances.Add(map.Tiles[i, k]);
											}
											room2.Entrances.Add(map.Tiles[i, j + 1]);
											room.Entrances.Add(map.Tiles[i, j + 1]);
											room.Entrances.Add(map.Tiles[i, room.Y - 1]);
											room2.Entrances.Add(map.Tiles[i, room.Y - 1]);
											connected = true;
											break;
										}
									}
									else if ((room.Y + room.H) < j
										  && (j - (room.Y + room.H)) <= roomConnectionDistance
										  && map.Tiles[i, j - 1].Type != TileTypes.Floor)
									{
										if (r.Next(101) <= prob)
										{
											for (int k = j - 1; k >= room.Y + room.H; k--)
											{  //bottom
												map.Tiles[i, k].Type = TileTypes.Floor;
												room.Entrances.Add(map.Tiles[i, k]);
												room2.Entrances.Add(map.Tiles[i, k]);
											}
											room2.Entrances.Add(map.Tiles[i, j - 1]);
											room.Entrances.Add(map.Tiles[i, j - 1]);
											room.Entrances.Add(map.Tiles[i, room.Y + room.H]);
											room2.Entrances.Add(map.Tiles[i, room.Y + room.H]);
											connected = true;
											break;
										}
									}
								}
								else if (j >= room.Y && j < room.Y + room.H)
								{
									if (room.X > i && room.X - i <= roomConnectionDistance
											&& map.Tiles[i + 1, j].Type != TileTypes.Floor)
									{
										if (r.Next(101) <= prob)
										{
											for (int k = i + 1; k < room.X; k++)
											{     //left
												map.Tiles[k, j].Type = TileTypes.Floor;
												room.Entrances.Add(map.Tiles[k, j]);
												room2.Entrances.Add(map.Tiles[k, j]);
											}
											room2.Entrances.Add(map.Tiles[i + 1, j]);
											room.Entrances.Add(map.Tiles[i + 1, j]);
											room.Entrances.Add(map.Tiles[room.X - 1, j]);
											room2.Entrances.Add(map.Tiles[room.X - 1, j]);
											connected = true;
											break;
										}
									}
									else if ((room.X + room.W) < i
										  && (i - (room.X + room.W)) <= roomConnectionDistance
										  && map.Tiles[i - 1, j].Type != TileTypes.Floor)
									{
										if (r.Next(101) <= prob)
										{
											for (int k = i - 1; k >= room.X + room.W; k--)
											{
												map.Tiles[k, j].Type = TileTypes.Floor;
												room.Entrances.Add(map.Tiles[k, j]);
												room2.Entrances.Add(map.Tiles[k, j]);
											}
											room2.Entrances.Add(map.Tiles[i - 1, j]);
											room.Entrances.Add(map.Tiles[i - 1, j]);
											room.Entrances.Add(map.Tiles[room.X + room.W, j]);
											room2.Entrances.Add(map.Tiles[room.X + room.W, j]);
											connected = true;
											break;
										}
									}
								}
							}
							if (connected)
							{
								room2.ConnectedRooms.Add(room);
								room.ConnectedRooms.Add(room2);
								break;
							}
						}
					}
				}
			}
		}

		/// <summary>
		/// Converts the Void tiles adjacent to every corridor Floor tile into Wall tiles (thus ensuring that no Floor tile is adjacent to any Void tiles).
		/// Also converts the corners of each room's walls into Wall tiles. (These haven't been converted during room placement because corner walls are not suitable as new room entrance positions.)
		/// </summary>
		/// <param name="map">The generated map</param>
		/// <param name="cols">The number of columns of the map grid</param>
		/// <param name="rows">The number of rows of the map grid</param>
		private static void AddWallsToCorridorsAndCorners(ref Map map, int rows, int cols)
		{
			Tile t, u;
			for (int j = 0; j < rows; j++)
			{
				for (int i = 0; i < cols; i++)
				{
					t = map.Tiles[i, j];
					if (t.Type == TileTypes.Floor && t.ContainingRoom == null) //corridor
					{
						for (int q = ((j == 0) ? 0 : (j - 1)); q <= (j >= rows - 1 ? (rows - 1) : (j + 1)); q++)
						{
							for (int w = (i == 0 ? 0 : (i - 1)); w <= (i >= cols - 1 ? (cols - 1) : (i + 1)); w++)
							{
								u = map.Tiles[w, q];
								if (u.Type == TileTypes.Void)
									u.Type = TileTypes.Wall;
							}
						}
					}
					else if (t.Type == TileTypes.Floor) //in room, check corners and turn them into walls
					{
						if (j > 0)
						{
							if (i > 0 &&
								map.Tiles[i - 1, j - 1].Type == TileTypes.Void &&
								map.Tiles[i, j - 1].Type == TileTypes.Wall &&
								map.Tiles[i - 1, j].Type == TileTypes.Wall)
							{
								map.Tiles[i - 1, j - 1].Type = TileTypes.Wall;
							}
							if (i < cols - 1 &&
								map.Tiles[i + 1, j - 1].Type == TileTypes.Void &&
								map.Tiles[i, j - 1].Type == TileTypes.Wall &&
								map.Tiles[i + 1, j].Type == TileTypes.Wall)
							{
								map.Tiles[i + 1, j - 1].Type = TileTypes.Wall;
							}
						}
						if (j < rows - 1)
						{
							if (i > 0 &&
								map.Tiles[i - 1, j + 1].Type == TileTypes.Void &&
								map.Tiles[i, j + 1].Type == TileTypes.Wall &&
								map.Tiles[i - 1, j].Type == TileTypes.Wall)
							{
								map.Tiles[i - 1, j + 1].Type = TileTypes.Wall;
							}
							if (i < cols - 1 &&
								map.Tiles[i + 1, j + 1].Type == TileTypes.Void &&
								map.Tiles[i, j + 1].Type == TileTypes.Wall &&
								map.Tiles[i + 1, j].Type == TileTypes.Wall)
							{
								map.Tiles[i + 1, j + 1].Type = TileTypes.Wall;
							}
						}
					}
				}
			}
		}
	}
}
